package demo10;

import java.util.regex.Pattern;

/*
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

 */
public class Test {
    public static void main(String[] args) {
        String content = "a*cfrgkkkkcfrga";

        String pattern = ".*cfrga*";
//        String content = "aab";
//
//        String pattern = "c*a*b*";
        System.out.println(pattern.length());

        boolean isMatch = Pattern.matches(pattern, content);
        System.out.println(isMatch);

        System.out.println(isMatch(content,pattern));
    }

//      网上提供的思路，大致如下
//    public static boolean isMatch(String s, String p) {
//        if(p.isEmpty()) return s.isEmpty();
//        boolean match = !s.isEmpty() && ((s.charAt(0) == p.charAt(0)) || p.charAt(0) == '.');
//        if(p.length() >= 2 && p.charAt(1) == '*') return isMatch(s, p.substring(2)) || (match && isMatch(s.substring(1), p));
//        return match && isMatch(s.substring(1), p.substring(1));
//    }


//经过内存优化，不适用charAt方法，减少因为栈而带来的时间以及内存消耗
    public static boolean isMatch(String s, String p) {
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        return isMatchChar(ss,0,pp,0);
    }
    public static boolean isMatchChar(char[] s,int sStart,char[] p,int pStart){
        //顺序读取
        if(pStart == p.length){
            //p是空字符串的时候，只有s也为空字符串才可匹配
            return s.length == sStart;
        }
        //当s串不为空字符串的时候，对当前字符进行匹配
        boolean match = !(s.length == sStart) && (s[sStart] == p[pStart] || p[pStart] == '.');
        //判断后续是否有*，有的话可以考虑要不要消除掉当前的p，以此分为两种情况
        if(p.length-pStart>=2 && p[pStart+1]=='*'){
            /*
                裁剪p||不裁剪p
                1.第一种情况，我们裁剪p，但是不需要裁剪s，因为我们不要当前的p做匹配
                2.第二种情况，我们不裁剪p，但是这有个前提，就是你的p当前指向的字符必须与s的匹配，不然不能保留p
             */
            return isMatchChar(s,sStart,p,pStart+2) || (match && isMatchChar(s,sStart+1,p,pStart));
        }
        /*
        如果p后面一个下标的符号没有*，那么我们直接把当前的p裁剪一位，当前，这个行为的前提是match为true
        而match为true的前提条件是 s串不为空串 以及 当前s和p所指向的字符相等
         */
        return match && (isMatchChar(s,sStart+1,p,pStart+1));
    }




}
